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)

8
votes
1answer
240 views

Digit Code Combination Problem

Based on real life experience, I just considered the following combinatorial challenge: In a workplace with currently $n$ employees each employee has its own unique 4-digit code used to pass ...
0
votes
1answer
38 views

How many totally ordered sets can be constructed from a given finite poset?

For a finite poset $S=\{x_1,\cdots,x_n\}$, there are $k$ ordering relations $x_{k_0}>x_{k_1}$ ($k_0\neq k_1$) that generate all the ordering of the poset $S$. Now we want to make $(S,\geq)$ a ...
3
votes
1answer
49 views

The largest subset of a finite cartesian product in which distinct elements differ in at least 2 components

Let $A_1,\ldots,A_n$ be finite sets of sizes $a_1,\ldots,a_n$. What is the largest possible size of a subset $S\subset\bigotimes A_k$ such that if $(d_1,\ldots,d_n),(e_1,\ldots,e_n)\in S$, then ...
2
votes
2answers
164 views

A combinatorial identity

In trying to prove the Taylor expansion of the Spread Polynomials as given ( also in Wikipedia ) by S Goh in a new way I miss a final decisive step. How to prove a combinatorial simplification for ...
3
votes
2answers
74 views

An efficient way to find anagrams

Consider a set of words where you want to divide the set into subsets of words, where all members of each subset are anagrams (same letters, different arrangement). You can do this computationally in ...
1
vote
0answers
38 views

Can this combinatoric sum be simplified?

Base cases: $F(n,k,d) = 0$ if $d=0$ and $n>0$ $F(n,k,d) = 1$ if $n=0$ Expression: $$F(n,k,d) = \sum_{s=0}^{\min(k,n)}\binom{n}{s}F(n-s,k,d-1)$$ I am trying to compute the value of $F(n,k,10)$ ...
4
votes
2answers
50 views

Self-avoiding rook walks on small rectangular chessboards (contest question)

I am not sure how to get a closed-form formula for $R(3,n)$ as the recursion involves a summation. Maybe the best that can be achieved is a recursion that does not involve a summation having an upper ...
1
vote
2answers
37 views

Broken Pens: combinations and probabilities

A container hold 50 pens. Exactly 10 pens are broken. What is the chance of finding: a) In a random sample of 10 drawn from the container, 2 or more are broken? b) The last broken pen to ...
2
votes
2answers
48 views

Understanding two “triangular” sequences

Just playing around doodling today and I happened across two related sequences of numbers and I'm reaching out to understand what exactly is going on. Sequence 1 The $n$th term of Sequence 1, $a_n$, ...
1
vote
3answers
35 views

Multiplying probablity

I am trying to help my kid do the following probability math. The language of the math baffles me. If the probability of the pictures tunring out is 1/5 then how can it become 3/4 (howeven numbers are ...
0
votes
2answers
48 views

Number of ways a page can be chosen so that sum of the digits is 9

A book contains 1000 pages.Number of ways a page can be chosen so that sum of the digits is 9;is equal to $\lambda$,then the value of $\frac{\lambda}{11}$ is ...
7
votes
3answers
103 views

Probability of rolling a dice 8 times before all numbers are shown.

What is the probability of having to roll a (six sided) dice at least 8 times before you get to see all of the numbers at least once? I don't really have a clue how to work this out. Edit: If we are ...
2
votes
1answer
60 views

Finding no. of triangles formed on a plane by 20 points

There are 20 points on a plane, no 3 are collinear except 4. Find no. of lines formed, and total no. of triangles that can be formed. ATTEMPT No of lines will be $$\binom{20}{2}-\binom{4}{2}+1 = ...
0
votes
0answers
46 views

How many n-digit sequences have exactly k 0's?

I think my homework question is missing some info. Ive posted the question exactly as stated. Am I correct that there is an error in the question?
2
votes
1answer
57 views

There are 3 workers in a company that has 5 working days in a week.

There are 3 workers in a company that has 5 working days in a week.In how many ways can the 3 workers take leave/rest if no two workers can take leave on the same day. Attempt: The first worker can ...
4
votes
2answers
82 views

Why does $\sum_{\sigma\in S_n}q^{\ell(\sigma)}=\frac{(1-q)(1-q^2)\cdots(1-q^n)}{(1-q)^n}$?

This is a known result, but I can't find a proof. Why does $$ \sum_{\sigma\in S_n}q^{\ell(\sigma)}=\frac{(1-q)(1-q^2)\cdots(1-q^n)}{(1-q)^n}? $$ Here $\ell(\sigma)$ is the length of $\sigma$, ...
1
vote
1answer
43 views

Counting no. of way 2 people who do not own a dog, and at least 2 people who don't own a cat given the info. below.

100 people have come to the annual pet owner's meeting. A quick show of hands demonstrates that 60 people own cats and 55 own dogs. Give the numerical answer and a brief explanation for the ...
5
votes
1answer
99 views

Decide if a given set of monomials is a basis of a polynomial ring quotient

Let $R = \mathbf{k}[x_1,\ldots,x_n]$ be a polynomial ring over some field $\mathbf{k}$ (which can be $\mathbb{C}$ if that makes a difference) and $I$ some ideal of $R$ such that $R/I$ is ...
-1
votes
3answers
52 views

Pick $x$ out of $y$ objects. Match $n$ picks.

Computer randomly picks a group of 6 objects out of 30, no repetitions. User than picks $6$ objects out of those $30$, also no repetitions. What are the odds of the user getting $3$ of his picks to ...
5
votes
1answer
64 views

Counting the expected number of strings with a given contiguous substring.

Question: Let a random bit string $x$ of length $n$ be given. What is the expected number of bit strings $w$ of length $2n$ that contain $x$ as a contiguous substring? What I know: For any bit ...
3
votes
1answer
54 views

How many ways are there to choose 16 cookies?

How many ways are there to choose 16 cookies if there are six varieties of cookies including chocolate chip, and at least six chocolate chip cookies must be chosen? Is $C(n+r-1,n-1)$ correct where ...
2
votes
2answers
51 views

Combination on a cycle?

A bracelet is to be made by threading four identical red beads and four identical yellow beads onto a hoop. How many different bracelets can be made? I imagine first to pick up one bead as a ...
0
votes
1answer
66 views

How to show that we reach $1$ at an odd or even turn without brute force

Consider the following challenge between two players A and B. They are given the initial terms $a_0= 3^{2014}$ and $b_0= 15^{4028}$ of two sequences, and the scope is to reach $1$ before the other, ...
1
vote
1answer
91 views

Number of increasing functions from $\{1,2,\dots, n\}$ to itself.

Let $f$ be a function from $X=\{1,2,3,...,n\}$ to itself. We say $f$ is increasing if $a\le b$ then $f(a)\le f(b)$. How do we find the number of increasing functions? I think if we can define ...
1
vote
3answers
45 views

Finding when list of numbers reach periodicity given known values

I'm trying to figure out when numbers reach "periodicity" given known values. I've included an example below with image: I have known sizes (100, 75, and 50) that I would like to know how many times ...
2
votes
2answers
53 views

Probability of Boys and Girls in Row

Ten male friends and six female friends line up next to the bus stop in a row. Everyone just positions themselves at random. What is the probability that no two females are sitting next to each other? ...
2
votes
1answer
35 views

Proof Check: Number of elements of $\mathbb{F}_{p^{n}}$ of the form $a^{p}-a$ for some $a \in \mathbb{F}_{p^{n}}$.

Consider the map $\varphi:\mathbb{F}_{p^{n}} \rightarrow \mathbb{F}_{p^{n}}$ defined by $x \mapsto x^{p}-x$. Since $(a+b)^{p}= a^{p}+b^{p}$ for all $a,b \in \mathbb{F}_{p^{n}}$ we have that $\varphi$ ...
0
votes
1answer
35 views

Probability of a run of *n* or more of some color from a subset of colors drawing without replacement?

I recently asked the question "Probability of a run of k or more of a subset of categories in m multinoulli trials?" with a very nice answer from member Tad. I'm trying to extend a result from a ...
2
votes
0answers
77 views

Conjecture on a graded ring

Consider $B^{(n)}=\mathbb{F}_2[X_1,\dots,X_n]/(X_1^2,\dots,X_n^2)=\bigoplus_{i=0}^nB_i^{(n)}$, where $B_i^{(n)}$ is the space of homogeneous elements of degree $i$. Notice that ...
0
votes
0answers
11 views

Smallest near triangulation of the plane with an external face of size $4$ for which all interior vertices have minimum degree $5$?

Consider the near-triangulation $G$ with an external face of size $4$. What is the minimum number of interior vertices for which G has minimum degree 5 as to those vertices? The degrees of the $4$ ...
0
votes
1answer
25 views

Probability of an event if the sample space has identical elements

Suppose we have a box, with only one small hole. Suppose 10 distinct black balls and 20 distinct white balls are put in the box. Now, in a random draw of 1 ball, the probability that the ball drawn is ...
2
votes
3answers
87 views

How many edges, faces, cells in a $2\times 2 \times 2 \times 2$ hyper cubic lattice?

If I have a $2\times 2\times 2\times 2$ hyper cubic lattice, how many corners, edges, faces, and cells will it be composed of? E.g. the 4D analogue of figure below. Assume the faces within the figure ...
0
votes
1answer
47 views

Combinatorics: Can anyone give a hint?

I'm practicing combinatorics then I got stuck in this problem. Suppose that I have an unlimited supply of identical math books, history books and physics books. All are the same size, and I have room ...
7
votes
3answers
312 views

“Mastermind”-esque safe opening problem.

I read this interview question for a trading job and it seems quite difficult. What is the technique to solving it? You have a safe with six digits and a light. You can input a code, if you have ...
6
votes
2answers
80 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?
11
votes
2answers
364 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
vote
2answers
73 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 ...
3
votes
3answers
90 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
votes
2answers
36 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 ...
2
votes
2answers
392 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 ...
2
votes
1answer
29 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$ ...
1
vote
0answers
35 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
32 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
42 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 ...
0
votes
1answer
24 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 ...
2
votes
3answers
145 views

Permutations of the elements of $\mathbb Z_p$

Let $p$ be prime. Describe all permutations $\sigma$ of the elements of $\mathbb Z_p$, having the property that $\{\sigma(i)-i: i\in\mathbb Z_p\}=\mathbb Z_p$ (Added by Robert Lewis in an attempt ...
0
votes
2answers
40 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
1answer
71 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
0answers
30 views

How many number of substrings of all lengths inclusive can be formed from a string of length n?

Options are A). $\dfrac{n(n-1)}2$ B). $\dfrac{n(n+1)}2$