For questions about the study of finite or countable discrete structures, specifically how to count or enumerate elements in a set (perhaps of all possibilities) or any subset. It includes questions on permutations, combinations, bijective proofs, and generating functions.

learn more… | top users | synonyms (4)

2
votes
1answer
31 views

Count the number of strings containing $ac$ or $ca$ for a fixed length over ternary alphabet $A = \{a,b,c\}$ using rational series

This question is a continuation the one asked here, and which already received good answers. Here I am asking for a solution using rational series of formal languages as suggested by the user J. E. ...
5
votes
6answers
5k views

If I buy 2 lottery tickets do I double my chance of winning?

There's a lottery. There are 6 balls chosen randomly from 49 and you have to match all the balls to win. I buy one ticket. If I buy two tickets with different numbers for the same draw, do I ...
2
votes
1answer
24 views

Degree of Polynomial in Centered Moments of Gamma$(n,1)$

I'm interested in the degree of the polynomial in $n$ of the expression for the $k$-th central moment $$ E((X_n - n)^k) $$ where $X_n$ is a Gamma$(n,1)$ random variable, that is, the sum of $n$ ...
2
votes
1answer
85 views

What is the number of set partitions of $\{1,1,2,2,3,3\}$?

It must be less than $B_6$ (where $B_6$ is the Bell number of $6$) since the elements are "duplicated". I would most appreciate a generating function that gives the number of set partitions of ...
5
votes
1answer
50 views

Derivative of sum of powers

For fixed $n \geq 1$ and $p \in [0,1]$, is there a nice expression for the derivative of $\sum_{k=0}^n p^k (1-p)^{n-k}$ with respect to p?
3
votes
2answers
53 views

Prof Gould combinatorial identity 3.27 and its “cousin” formula

In the book on Combinatorial Identities of Prof Gould I found the identity 3.27 $$\sum_{k=0}^{\rho}\binom{2x+1}{2k+1}\binom{x-k}{\rho-k}=\frac{2x+1}{2\rho+1}\binom{x+\rho}{2\rho}2^{2\rho}$$ I now ...
1
vote
0answers
38 views

Minimum Cake Cutting for a Party

You are organizing a party. However, the number of guests to attend your party can be anything from $a_1$, $a_2$, $\ldots$, $a_n$, where the $a_i$'s are positive integers. You want to be ...
-1
votes
2answers
30 views

Does the order in a circular arrangement matter?

I posted a question a while ago: Ten chairs are arranged in a circle. Find the number of subsets of this set of chairs that contain at least three adjacent chairs. My question here is: imagine a ...
1
vote
2answers
41 views

Seating people in a circular table

It has always been an interesting question. If we have $10$ chairs and a round table, how many ways are there of seating $10$ people? I would say there are $10!$ ways to seat the people due to ...
2
votes
3answers
370 views

Stars and Bars vs PIE

I randomly made up this question so I could check: There are $3$ kids and $6$ gifts, how many ways to distribute so that each kid has at least one gift. Obviously, $**|**|**$ there are ...
3
votes
1answer
55 views

find a group of lowest N numbers so that no 2 pairs have the same bitwise or

I am trying to find the lowest group of N numbers (i.e. N=1000) so that no 2 pairs from the group have the same bit-wise or. more specific need to find a group $A = \{a_1,a_2,a_3,..,a_N\} $ such ...
42
votes
16answers
11k views

Good Book On Combinatorics

What is your recommendation for an in-depth introductory combinatoric book? A book that doesn't just tell you about the multiplication principle, but rather shows the whole logic behind the questions ...
2
votes
2answers
127 views

Union of two matching sets being a matching

Let $G$ be a bipartite graph with parts $A$ and $B$. Let $U\subseteq A$ and $V\subseteq B$ and assume that there exists matching in $G$ that covers all vertices in $U$ and another matching that covers ...
1
vote
0answers
23 views

A question regarding matchings in bipartite graphs

Let $G=(V,E)$ be a graph with $V(G)=X\cup Y$, let $M_1$ be a matching that "covers" $X'\subseteq X$, and let $M_2$ be a matching that "covers" $Y'\subseteq Y$. Show that then there is a matching $M$ ...
5
votes
1answer
27 views

$n$-vertex $3$-edge-colored graphs with exactly $6$ automorphisms which preserve edge color classes, but permute the edge colors distinctly?

In each of these $3$-edge-colored graphs, there are exactly $6$ automorphisms which preserve the set of edge color classes: (These automorphisms don't necessarily map e.g. green edges to green ...
2
votes
1answer
41 views

how many strings are length 10 with 5 1's and 5 0's are there?

I used generating functions and got $A(x,y)=(x+y)^{10}$. Then I found the coefficient of the $x^5y^5$ and got $252$. Is that the correct answer?
6
votes
3answers
1k views

People sitting in a circle chewing gum

Ten people are sitting in a circle of ten chairs, chewing gum. Each person spits out his or her gum and places it either under his or her own chair or under an immediately adjacent chair. How many ...
1
vote
1answer
64 views

Permutation of numbers from multiple sets [May contain duplicate numbers among other sets], resulting in Non-Duplicate Set

We have 3 Data Sets. From each set we will be selecting few numbers. 3 from Set 1, 2 from Set 2, 3 from Set 3. Totally, we will get 8 Numbers from 3 Sets. The resulting sets shouldn't contain any ...
0
votes
1answer
14 views

Inverse function for a sort of negative binomial distribution

I am trying to find the inverse function of $f(p) = \sum_{k=0}^{6}{\binom{6-H+k}{k} p^{7-H} (1-p)^k}$, where $0 \leq H \leq 6$ is a constant integer. Any ideas on how to do this? Or perhaps equally ...
2
votes
2answers
977 views

Every $k$ vertices in an $k$ - connected graph are contained in a cycle.

Let $G$ be a $k$-connected graph. Meaning, $G$ has no less than $k$ vertices, and for every set of $k-1$ or less vertices, if we remove them from $G$, the graph stays connected (Of course, $G$ itself ...
1
vote
1answer
75 views

Permutations of the elements of $\mathbb Z_p$

Note Added by Robert Lewis, 2 August 2015 3:04 PM PST in an attempt to provide background, motivation, and other context for this engaging problem: This problem essentially asks for a method of ...
1
vote
2answers
22 views

How many sequences $(i_1,\ldots,i_d)$ of fixed length `d` of positive integers satisfy $\alpha\le i_1+\cdots+i_d\le\beta$?

Let $i\in\mathbb N^d$ and $|i|:=i_1+\cdots+i_n$. How can we calculate the cardinality of the set of all $i$ which satisfy $$\alpha\le|i|\le\beta$$ with given constants $\alpha,\beta\in\mathbb N$?
4
votes
1answer
36 views

Mathematics of Magic Squares

I have seen many popular accounts of simple magic squares but I would like to find a proper mathematical background to understanding magic squares. What background knowledge do I need. I am a retired ...
0
votes
2answers
31 views

Probability of picking up one ball of each color

A box contains 6 red, 4 white and 5 black balls. A person draws 4 balls from the box at random. Let P be the probability that among the balls drawn there is at least one ball of each color. Find 455 * ...
0
votes
2answers
55 views

How many divisors of the combination of numbers?

Find the number of positive integers that are divisors of at least one of $A=10^{10}, B=15^7, C=18^{11}$ Instead of the PIE formula, I would like to use intuition. $10^{10}$ has $121$ divisors, ...
0
votes
1answer
23 views

Basic doubt on Stirling numbers of Second Type

When learning Stirling numbers of Second Type, one simple doubt came to my mind and posting it here. The formula for Stirling numbers of Second Type is given as ...
0
votes
1answer
45 views

How many combinations in 10x10x10 Rubik's cube?

I was wondering how many possible combinations there is in the cubes greater than 3x3x3 (4x4x4, 5x5x5, ..., 10x10x10)? We know that in 3x3x3 there are about 4,3 * 10^19 combinations, what about bigger ...
3
votes
2answers
44 views

Find the least $N$ so there is no square

Find the least positive integer $N$ such that the set of $1000$ consecutive integers beginning with $1000 \cdot N$ contains no square of an integer. Let $x^2$ appear before $1000N$ so: $(x+1)^2 ...
-3
votes
0answers
28 views
0
votes
0answers
23 views

Find the constant $k$

In a graph $G$ with $n$ vertices, let $T_1$ be the number of triangles one can make and $T_2$ be the numbers of tetrahedrons. Find the least constant $k$ such that $(T_2)^3\le k.(T_1)^4$.
12
votes
0answers
234 views
+100

Finding real money on an even stranger weighing device

You have $n$ coins which each weigh either $20$ grams or $10$ grams. Each is labelled from $0$ to $n-1$ so you can tell the coins apart. You have one weighing device as well. At the first turn you ...
0
votes
0answers
73 views

Zero-Sum Partitions of Nonzero Elements of a Ring

In this question, rings are not necessarily finite nor do they need to be unital (i.e., the multiplicative identity may not exist). Although I shall almost exclusively discuss finite commutative ...
2
votes
1answer
37 views

Probability of a run of *k* or more of a subset of categories in *m* multinoulli trials?

Given a multinoulli distribution of categories $(C_1,C_2,...,C_n)$ with associated probabilities $\left\{p_1,p_2,\ldots ,p_n\right\}$ with $\sum _{i=1}^n p_i=1$, is there a tractable way to get the ...
1
vote
0answers
106 views

Average Degree of a Random Geometric Graph

A set of $N$ points are distributed randomly on a unit square with uniform distribution. Two points $\mathbf{p}_i$ and $\mathbf{p}_j$ are said to be connected if $\|\mathbf{p}_i - \mathbf{p}_j\| \leq ...
1
vote
1answer
37 views

How to use Principle of Inclusion-Exclusion here?

A while ago I posted a question: Coloring a Grid. Online, I seem to have stumbled upon a usage of PIE AOPS Wiki Solution AIME II #9. (1) Now, I have experience with PIE, but I do not see how to ...
1
vote
1answer
64 views

Expected Value of a Mosquito

A mosquito is walking at random on the nonnegative number line. She starts at $1$. When she is at $0$, she always takes a step $1$ unit to the right, but, from any positive position on the line, she ...
2
votes
1answer
36 views

An easy (or not?) collection of proper sets .

Let $S$ be a finite set. We are given $k$ rows and in each row we have two subsets of $S$ which we call them $A_i$, $B_i$ (for the $i$th row, with $i\leq k$). $A_1$ and $B_1$ $A_2$ and $B_2$ . . ...
9
votes
2answers
215 views

Help with binomial identity

In my work, I was led to the following identity. I would be grateful if someone could provide an easy proof. Suppose $n, d, k \in \mathbb{Z}$, and $d \geq 0$. $$ \sum_{j = 0}^d (-1)^{d-j} \cdot ...
19
votes
4answers
9k views

The generating function for the Fibonacci numbers

Prove that $$1+z+2z^2+3z^3+5z^4+8z^5+13z^6+...=\frac{1}{1-(z+z^2)}$$ The coefficients are Fibonacci numbers, i.e., the sequence $\left\{1,1,2,3,5,8,13,21,...\right\}$.
4
votes
2answers
91 views

Combinatoric Birthday Paradox

There is likely a closed form solution for this problem but it's had me puzzled for days. This is about a variant on the classic birthday paradox. To recap, the birthday paradox is where given only 23 ...
0
votes
3answers
51 views

Why is it true that $(a_1 \ a_2 \dots a_r) = (a_1 \ a_r)(a_1 \ a_{r-1})\dots(a_1 \ a_3)(a_1 \ a_2)$?

In the theory of permutation, a $r$-cycle $(a_1 a_2...a_r)$ is defined in the following way: Start from $a_i$, a permutation function $f$ sends $a_i$ to $a_{i+1}$. When $i=r, a_i \text{ will be ...
-1
votes
2answers
48 views

Circular table problem

I've looked other questions that might help solve my problem, but haven't found any people who've used my method to solve it. The problem goes like this: Suppose there are 7 men and 5 women, and they ...
3
votes
1answer
53 views

How many ways can you choose team of 5 people out of 7 men and 6 women in which there are at least 3 men?

I am confused by this question. I solved it by selecting 3 men first out of 7 men and then selecting 2 people out of 10 remaining person ( 4 men and 6 women ) . So my answer is C(7,3) * C(10,2) = ...
-2
votes
0answers
49 views

Summation of prime multiples less than n

How can I sum the following $$ \sum (2^x\cdot3^y\cdot5^z\cdot7^w\cdot\prod_1^m(p_i^{a_i})) $$ with $$2^x\cdot3^y\cdot5^z\cdot7^w\cdot\prod_1^m(p_i^{a_i}) \le n$$ where $p_i \ge 11$ are list of fixed ...
26
votes
1answer
565 views

Generating function solution to previous question $a_{n}=a_{\lfloor n/2\rfloor}+a_{\lfloor n/3 \rfloor}+a_{\lfloor n/6\rfloor}$

In attempting to answer this question, I reduced it to a seemingly simple generating functions question, but after days of work was unable to construct a proof. Since I do not have experience trying ...
2
votes
1answer
24 views

Probability a card can win a trick with a trump suit

I'm working on the AI for a card game that uses a standard deck of 52 cards consisting of 13 cards in 4 (spades, clubs, diamonds, hearts) suits. Each player starts with 13 cards in their hand. ...
5
votes
0answers
100 views
+50

If $G$ is shellable, then $G \backslash \{x_i\}$ is shellable?

A simplicial complex $\Delta$ on the vertex set $\{x_1,\dots,x_n\}$ is shellable if the facets of $\Delta$ can be ordered, say $F_ 1 , . . . , F _s$, such that for all $1 \leq i < j ...
2
votes
1answer
50 views

Counting number of bijections

The question is: Let $S = \{a,b,c,d\}$ and let $X : = \{f\colon S \to S \mid f \, \, \text{is bijective and } f(x) \ne x \, \, \text{for each}\, \, x \in S \}$. What is $|X|$? Is there a simple ...
3
votes
2answers
104 views

Algebraic proof that $\sum\limits_{i=0}^n \binom{i}{k} = \binom{n + 1}{k + 1}$

I'm looking for an algebraic proof of this identity for $n, k \in \mathbb{N}$: $$\sum\limits_{i=0}^n \binom{i}{k} = \binom{n + 1}{k + 1}$$ So far, I've turned the left hand side of the equality into ...
6
votes
0answers
41 views

A combinatorial proof by tesselation of the plane.

Some days ago the following problem was posed in the site: given a set of $N$ points in the plane such that for each pair of points $p,q$ we have $\lVert p-q\rVert >1$, prove there is a subset of ...